using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace WOWEquipOptimizer
{
    /// <summary>
    /// Genetic Algorithm, many individuals with different equip are evaluated, selected and mutated
    /// </summary>
    public class OptimizeFull : Optimizer
    {
        struct ThreadState
        {
            public ulong Hash;
            public int Start;
            public int Stop;
            public AutoResetEvent Event;
            public Individual[] Individuals;
            public Character Target;
            public ThreadState(ulong hash, int start, int stop, WaitHandle reset, ref Individual[] individuals, ref Character target)
            {
                Hash = hash;
                Start = start;
                Stop = stop;
                Event = (AutoResetEvent) reset;
                Individuals = individuals;
                Target = target;
            }
        }
        struct Individual : IComparable, IComparer<Individual>
        {
            private Item[] m_Genes;

            public Item[] Genes
            {
                get { return m_Genes; }
                set
                {
                    m_Genes = value;
                }
            }
            public Item this[SlotName key]
            {
                get
                {
                    return m_Genes[(int)key];
                }
                set
                {
                    m_Genes[(int)key] = value;
                }
            }
            public Item this[int key]
            {
                get
                {
                    return m_Genes[key];
                }
                set
                {
                    m_Genes[key] = value;
                }
            }

            public int Generation;
            public float Fitness;
            public ulong Hash;
            public bool School;
            public Individual(Item[] genes)
            {
                m_Genes = genes;
                Generation = 0;
                Fitness = 0;
                Hash = Item.GetHashCode(m_Genes);
                School = false;
            }
            #region IComparable Member

            public int CompareTo(object obj)
            {
                Individual cmp = (Individual)obj;
                if (Fitness < cmp.Fitness) return -1;
                else if (Fitness == cmp.Fitness) return 0;
                else return 1;
            }
            #endregion

            #region IComparer<Individual> Member

            public int Compare(Individual x, Individual y)
            {
                if (x.Hash > y.Hash) return 1;
                else if (x.Hash == y.Hash) return 0;
                else return -1;
            }

            #endregion

        }
        Individual[] m_Individuals;
        int m_CurrentGeneration = 0;
        private int m_MaxPopulation = 1000;
        private int m_Mutatecounter = 0;
        private int cpucount = Environment.ProcessorCount;
        private bool m_Found = false;
        private WaitHandle[] m_WaitHandles;
        public OptimizeFull()
        {

        }
        // shell sort is faster with previously sorted arrays
        private void ShellSort(ref Individual[] array)
        {

            for (int increment = array.Length / 2; increment > 0; increment = (increment == 2 ? 1 : (int)((increment / 2.2) + 0.5)))
            {
                for (int i = increment; i < array.Length; i++)
                {
                    for (int j = i; j >= increment && array[j - increment].Fitness > array[j].Fitness; j -= increment)
                    {
                        Individual temp = array[j];
                        array[j] = array[j - increment];
                        array[j - increment] = temp;
                    }
                }
            }
        }
        /// <summary>
        /// Thread function for the optimization of individuals
        /// </summary>
        /// <param name="stateobject"></param>
        private void OptimizeIndividual(object stateobject)
        {
            ThreadState ts = (ThreadState)stateobject;
            for (int i = ts.Start; i < ts.Stop; i++)
            {
                if (Optimizer.m_Abort) break;
                Individual indiv = ts.Individuals[i];
                ts.Target.Slots = indiv.Genes;
                base.m_Target = ts.Target;
                base.EnableNotification = false;
                base.MaxTV = indiv.Fitness;
                base.Optimize();
                indiv.Genes = ts.Target.Slots;
                indiv.Fitness = base.MaxTV;
                indiv.Hash = Item.GetHashCode(indiv.Genes);
                ts.Individuals[i] = indiv;
            }
            ts.Event.Set();
        }
        /// <summary>
        /// Thread function for evaluating one individual
        /// </summary>
        /// <param name="stateobject"></param>
        private void EvalIndividual(object stateobject)
        {
            ThreadState ts = (ThreadState)stateobject;
            for (int i = ts.Start; i < ts.Stop; i++)
            {
                Individual indiv = ts.Individuals[i];
                if (indiv.Fitness == 0 && indiv.Genes != null)
                {
                    Monitor.Enter(ts.Target);
                    try
                    {
                        indiv.Fitness = -1;
                        bool valid = ts.Target.evaluateEquip(indiv.Genes);
                        if(valid) indiv.Fitness = ts.Target.evaluateTF();
                    }
                    finally
                    {
                        m_Individuals[i] = indiv;
                        Monitor.Exit(ts.Target);
                    }
                }
                if (Optimizer.m_Abort) break;
            }
            ts.Event.Set();
        }
        /// <summary>
        /// tread function for the finding clones
        /// </summary>
        /// <param name="stateobject"></param>
        private void FindIndex(object stateobject)
        {
            ThreadState ts = (ThreadState)stateobject;
            for (int i = ts.Start; i < ts.Stop; i++)
            {
                if (m_Found)
                {
                    break;
                }
                if (ts.Individuals[i].Hash == ts.Hash)
                {
                    m_Found = true;
                    break;
                }
                if (m_Abort) break;
            }
            ts.Event.Set();
        }
        // Multithreaded FindIndex
        private bool CheckIndex(int start, int stop, ulong hash)
        {
            m_Found = false;
            int segment = (stop-start)/cpucount;
            for (int i = 0; i < cpucount; i++)
            {
                (m_WaitHandles[i] as AutoResetEvent).Reset();
                ThreadPool.QueueUserWorkItem(new WaitCallback(FindIndex), new ThreadState(hash, start + i * segment, start + (i + 1) * segment, m_WaitHandles[i], ref m_Individuals, ref m_Target));
            }
            WaitHandle.WaitAll(m_WaitHandles);
            return m_Found;
        }
        // Multithreaded EvalIndividual
        private void EvalIndivWrapper(int start, int stop)
        {
            /*
            int segment = (stop - start) / cpucount;
            ulong hash = 0;
            for (int i = 0; i < cpucount; i++)
            {
                (m_WaitHandles[i] as AutoResetEvent).Reset();
                ThreadPool.QueueUserWorkItem(new WaitCallback(EvalIndividual), new ThreadState(hash, start + i * segment, start + (i + 1) * segment, m_WaitHandles[i], ref m_Individuals, ref m_Target));
            }
            WaitHandle.WaitAll(m_WaitHandles);
            */
            for (int i = start; i < stop; i++)
            {
                Individual indiv = m_Individuals[i];
                indiv.Fitness = -1;
                bool valid = m_Target.evaluateEquip(indiv.Genes);
                if (valid) indiv.Fitness = m_Target.evaluateTF();
                m_Individuals[i] = indiv;
            }
        }
        // Multithreaded OptimizeIndividual
        private void OptimizeIndivWrapper(int start, int stop)
        {
            /*
            int segment = (stop - start) / cpucount;
            ulong hash = 0;
            for (int i = 0; i < cpucount; i++)
            {
                (m_WaitHandles[i] as AutoResetEvent).Reset();
                ThreadPool.QueueUserWorkItem(new WaitCallback(OptimizeIndividual), new ThreadState(hash, start + i * segment, start + (i + 1) * segment, m_WaitHandles[i], ref m_Individuals, ref m_Target));
            }
            WaitHandle.WaitAll(m_WaitHandles);
            */
            for (int i = start; i < stop; i++)
            {
                if (Optimizer.m_Abort) break;
                Individual indiv = m_Individuals[i];
                m_Target.Slots = indiv.Genes;
                base.m_Target = m_Target;
                base.EnableNotification = false;
                base.MaxTV = indiv.Fitness;
                base.Optimize();
                indiv.Genes = m_Target.Slots;
                indiv.Fitness = base.MaxTV;
                indiv.Hash = Item.GetHashCode(indiv.Genes);
                m_Individuals[i] = indiv;
            }
        }
        private bool Valid(Individual input)
        {
            return Valid(input, false);
        }
        // Check for validity of unique m_Items
        private bool Valid(Individual input, bool full)
        {
            int start = full ? 0 : m_MaxPopulation / 2;
            if (CheckIndex(start, m_MaxPopulation, input.Hash) && m_LockCount <= 5)
            {
                return false;
            }
            return true;
        }
        // mutate until we have array valid individual again
        private Individual Mutate(Individual input, int index)
        {
           m_Mutatecounter++;
           if (m_Mutatecounter > 100) return input;
           Individual retval = input;
           int slot = m_Random.Next(0, Character.SlotCount);
           if (m_Items[slot].Count == 1) return Mutate(input,index);
           if (m_Locks[slot]) return Mutate(input,index);
           Item newitem = m_Items[slot][m_Random.Next(m_Items[slot].Count - 1) + 1];
           if (newitem.SocketCount > 0)
           {
               for (int m = 0; m < newitem.SocketCount; m++)
               {
                   Gem gem = (Gem)m_Items[m_Items.Length - 1][m_Random.Next(m_Items[m_Items.Length - 1].Count - 1) + 1];
                   if (newitem.GemColors[m] == GemType.Meta) continue;
                   newitem.Gems[m] = gem;
               }
           }
           newitem.Enchant = getEnchant(newitem, slot);
           retval[slot] = newitem;
           input.Hash = Item.GetHashCode(retval.Genes);
           if (Valid(retval))
           {
               retval.Fitness = 0;
               return retval;
           }
           else return Mutate(input, index);
        }
        /// <summary>
        /// we try to optimize the worst item in our gear, based on the ilvl
        /// </summary>
        /// <param name="m_Items"></param>
        /// <param name="slot"></param>
        /// <returns></returns>
        private Individual School(Individual input, int slot)
        {
            Individual retval = input;
            if (m_Items[slot].Count == 1) return input;
            if (m_Locks[slot]) return input;
            Item newitem = m_Items[slot][m_Random.Next(m_Items[slot].Count - 1) + 1];
            if (newitem.SocketCount > 0)
            {
                for (int m = 0; m < newitem.SocketCount; m++)
                {
                    Gem gem = (Gem)m_Items[m_Items.Length - 1][m_Random.Next(m_Items[m_Items.Length - 1].Count - 1) + 1];
                    if (newitem.GemColors[m] == GemType.Meta) continue;
                    newitem.Gems[m] = gem;
                }
            }
            newitem.Enchant = getEnchant(newitem, slot);
            retval[slot] = newitem;
            if (Valid(retval))
            {
                retval.Fitness = 0;
                return retval;
            }
            else return School(input, slot);
        }
        /// <summary>
        /// throw out bad oens
        /// </summary>
        /// <param name="m_Items"></param>
        /// <param name="max"></param>
        private void Selection(ref Individual[] input, int max)
        {
            //Array.Sort(m_Items);
            ShellSort(ref input);
            int counter = 0;
            int length = input.Length;
            m_MaxTV = input[length - 1].Fitness;
            while (counter < max)
            {
                int index = 0;
                do
                {
                    index = m_Random.Next((int)(length * 0.75f + 0.5));
                }
                while (input[index].Fitness == 0);
                input[index].Fitness = 0;
                counter++;
            }
            ShellSort(ref input);
        }
        /// <summary>
        /// crossover of two individuals, random xo point
        /// </summary>
        /// <param name="p1"></param>
        /// <param name="p2"></param>
        /// <returns></returns>
        private Individual Crossover(Individual p1, Individual p2)
        {
            Item[] genes = new Item[p1.Genes.Length];
            int crossoverpoint = m_Random.Next(p1.Genes.Length/4,p1.Genes.Length*3/4);
            if(m_Random.NextDouble() < 0.5)
            {
                Array.Copy(p1.Genes, 0, genes, 0, crossoverpoint);
                Array.Copy(p2.Genes, crossoverpoint, genes, crossoverpoint, p2.Genes.Length - crossoverpoint);
            }
            else
            {
                Array.Copy(p2.Genes, 0, genes, 0, crossoverpoint);
                Array.Copy(p1.Genes, crossoverpoint, genes, crossoverpoint, p1.Genes.Length - crossoverpoint);
            }
            Individual child = new Individual(genes);
            child.Generation = Math.Max(p1.Generation, p2.Generation) + 1;
            child.Hash = Item.GetHashCode(child.Genes);
            return child;
        }
        /// <summary>
        /// wrapper to return a proper enchant
        /// </summary>
        /// <param name="item"></param>
        /// <param name="slot"></param>
        /// <returns></returns>
        private Enchant getEnchant(Item item, int slot)
        {
            List<Enchant> enchants = Enchant.Enchants[slot];
            if (item.Id == Item.NoneId) return Enchant.None;
            if (item.GetType() == typeof(Weapon))
            {
                if ((item as Weapon).TwoHand)
                {
                    enchants = Enchant.TwoHand;
                }
            }
            else if (item.GetType() == typeof(Armor))
            {
                if ((item as Armor).Type == ArmorProficiency.Shield)
                {
                    enchants = Enchant.Shield;
                }
            }
            if (enchants.Count > 1)
            {
                return enchants[m_Random.Next(enchants.Count - 1) + 1];
            }
            return Enchant.None;
        }
        /// <summary>
        /// main optimization routine with loop
        /// </summary>
        public override void Optimize()
        {
            m_Abort = false;
            m_WaitHandles = new WaitHandle[cpucount];
            for (int i = 0; i < cpucount; i++)
            {
                m_WaitHandles[i] = new AutoResetEvent(false);
            }
            int maxtime = 5;
            m_MaxPopulation = 4000;
            m_MaxPopulation -= m_LockCount * m_MaxPopulation / 20;
            m_Individuals = new Individual[m_MaxPopulation];
            int mutationrate = m_MaxPopulation / 10;
            int schoolrate = m_MaxPopulation / 10;
            m_CurrentGeneration = 0;
            float besttv = 0;
            int bestgeneration = 0;
            DateTime start = DateTime.Now;
            int indivcount = 0;
            while (indivcount < m_MaxPopulation)
            {
                Item[] items = new Item[m_Target.Slots.Length];
                for (int k = 0; k < m_Target.Slots.Length; k++)
                {
                    Item newitem = Item.getPlaceholderItem(k);
                    newitem.Enchant = Enchant.None;
                    if (m_Locks[k])
                    {
                        items[k] = m_Target.Slots[k];
                    }
                    else
                    {
                        if (m_Items[k].Count > 1)
                        {
                            newitem = m_Items[k][m_Random.Next(m_Items[k].Count - 1) + 1];
                            if (newitem.SocketCount > 0)
                            {
                                for (int m = 0; m < newitem.SocketCount; m++)
                                {
                                    Gem gem = (Gem)m_Items[m_Items.Length - 1][m_Random.Next(m_Items[m_Items.Length - 1].Count - 1) + 1];
                                    if (newitem.GemColors[m] == GemType.Meta) continue;
                                    newitem.Gems[m] = gem;
                                }
                            }
                        }
                        newitem.Enchant = getEnchant(newitem, k);
                        items[k] = newitem;

                        if (newitem.GetType() == typeof(Weapon) && ((Weapon)newitem).TwoHand)
                        {
                            items[k + 1] = Weapon.None;
                            k++;
                        }
                    }
                }
                Individual add = new Individual(items);

                if (Valid(add, true))
                {
                    m_Individuals[indivcount] = add;
                    indivcount++;
                }
            }
            if (indivcount < m_Individuals.Length)
            {
                Array.Resize(ref m_Individuals, indivcount);
            }
            EvalIndivWrapper(0, m_Individuals.Length);
            ShellSort(ref m_Individuals);
            while ((DateTime.Now.Ticks - start.Ticks) < maxtime * TimeSpan.TicksPerMinute)
            {
                EvalIndivWrapper(0, m_Individuals.Length / 2);
                //selection, just array certain amount of our parents survive to have sex
                Selection(ref m_Individuals, m_MaxPopulation / 2);
                //sex
                indivcount = 0;
                while (indivcount < m_MaxPopulation / 2)
                {
                    Individual p1 = m_Individuals[m_MaxPopulation / 2 + m_Random.Next(m_MaxPopulation / 2)];
                    Individual p2 = m_Individuals[m_MaxPopulation / 2 + m_Random.Next(m_MaxPopulation / 2)];
                    if (p1.Hash == p2.Hash)
                    {
                        continue;
                    }
                    Individual child = Crossover(p1, p2);
                    if (Valid(child))
                    {
                        m_Individuals[indivcount] = child;
                        indivcount++;
                    }
                }
                // mutation
                indivcount = 0;
                while (indivcount < mutationrate)
                {
                    int index = m_Random.Next(m_MaxPopulation / 2); // make sure we just mutate the new ones
                    Individual indiv = m_Individuals[index];
                    m_Mutatecounter = 0;
                    m_Individuals[index] = Mutate(indiv, index);
                    indivcount++;
                }
                // school
                indivcount = 0;
                while (indivcount < m_MaxPopulation / 2)
                {
                    int index = m_Random.Next(m_MaxPopulation / 2); // make sure we just educate the new ones
                    Individual indiv = m_Individuals[index];
                    int ilvl = indiv.Genes[0].Level;
                    int slot = 0;
                    for(int i = 0;i<indiv.Genes.Length;i++)
                    {
                        if (indiv.Genes[i].Id != Item.NoneId)
                        {
                            if (ilvl > indiv.Genes[i].Level)
                            {
                                ilvl = indiv.Genes[i].Level;
                                slot = i;
                            }
                        }
                    }
                    m_Individuals[index] = School(m_Individuals[index],slot);
                    indivcount++;
                }
                if (m_MaxTV > besttv)
                {
                    besttv = m_MaxTV;
                    bestgeneration = m_CurrentGeneration;
                }
                if ((m_CurrentGeneration - bestgeneration) > 100 || m_Abort) break;
                m_CurrentGeneration++;
                UpdateGraphics(m_MaxTV);
            }
            EvalIndivWrapper(0, m_Individuals.Length);
            if (!m_Abort)
            {
                OptimizeIndivWrapper((int)(m_Individuals.Length * 0.975f), m_Individuals.Length);
            }
            ShellSort(ref m_Individuals);
            Individual indi = m_Individuals[m_Individuals.Length - 1];
            m_Target.Slots = (Item[]) indi.Genes.Clone();
            Notify();
        }
    }
}
